﻿public struct BinarySearchTree
{
    private TreeNode root;

    public BinarySearchTree(TreeNode root)
    {
        this.root = root;
    }

    public TreeNode Root
    {
        get
        {
            return root;
        }
        set
        {
            root = value;
        }
    }

    public void Add(TreeNode node)
    {
        Add(root, node);
    }

    public void Delete(int value)
    {
        TreeNode nodeToBeDeleted = Find(root, value);
        Delete(nodeToBeDeleted);
    }

    public TreeNode Find(int value)
    {
        TreeNode searchedNode = Find(root, value);
        return searchedNode;
    }

    private void Add(TreeNode root, TreeNode node)
    {
        if (root == null)
        {
            root = node;
            return;
        }
        else if (root.Value == node.Value)
        {
            TreeNode rightPart = root.Right;
            root.Right = node;
            node.Right = rightPart;
        }
        else
        {
            if (root.Value >= node.Value)
            {
                Add(root.Right, node);
            }
            else
            {
                Add(root.Left, node);
            }
        }
    }

    private void Delete(TreeNode nodeToBeDeleted)
    {
        TreeNode parent = null;
        if (nodeToBeDeleted != root)
        {
            parent = FindParent(root, nodeToBeDeleted);
        }
        if (HasNoChildren(nodeToBeDeleted))
        {
            if (parent.Left == nodeToBeDeleted)
            {
                parent.Left = null;
            }
            else
            {
                parent.Right = null;
            }
        }
        else
        {
            if (parent == null)
            {
                ReplaceNodeWithChild(root);
            }
            else
            {
                ReplaceNodeWithChild(parent);
            }
        }
    }

    private TreeNode Find(TreeNode root, int value)
    {
        if (root.Value == value)
        {
            return root;
        }
        else
        {
            TreeNode searchedNode = null;
            if (root.Value >= value)
            {
                searchedNode = Find(root.Right, value);
            }
            else
            {
                searchedNode = Find(root.Left, value);
            }
            return searchedNode;
        }
    }

    private TreeNode FindParent(TreeNode root, TreeNode child)
    {
        if (root.Left == child)
        {
            return root;
        }
        else if (root.Right == child)
        {
            return root;
        }
        else
        {
            TreeNode parent = null;
            parent = FindParent(root.Left, child);
            if (root == null)
            {
                parent = FindParent(root.Right, child);
            }
            return parent;
        }
    }

    private TreeNode FindSuccessor(TreeNode node)
    {
        if (node.Left == null && node.Right == null)
        {
            return node;
        }
        else
        {
            TreeNode child = FindSuccessor(node.Left);
            return child;
        }
    }

    private bool HasNoChildren(TreeNode nodeToBeDeleted)
    {
        bool hasNoChildren = true;
        if (nodeToBeDeleted.Left != null || nodeToBeDeleted.Right != null)
        {
            hasNoChildren = false;
        }
        return hasNoChildren;
    }

    private void ReplaceNodeWithChild(TreeNode node)
    {
        if (node.Left == null)
        {
            node = node.Right;
        }
        else if (node.Right == null)
        {
            node = node.Left;
        }
        else
        {
            TreeNode child = FindSuccessor(node.Right);
            child.Right = node.Right;
            child.Left = node.Left;
            node = null;
        }
    }
}